import java.util.ArrayList;
import java.util.Stack;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-05-30
 * Time: 13:13
 */
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
public class Solution2 {
    public int[] inorderTraversal (TreeNode root) {
        //还是利用栈的思想完成中序遍历
        if(root==null){
            return new int[0];
        }
        Stack<TreeNode> stack=new Stack<>();
        ArrayList<Integer> list=new ArrayList<>();
        while ( root!=null || !stack.isEmpty() ){
            //先遍历到最左边
            while ( root!=null ){
                stack.push( root );
                root=root.left;
            }
            //加入根节点
            TreeNode cur=stack.pop();
            list.add( cur.val );
            //遍历右边
            root=cur.right;
        }
        int[] ret=new int[list.size()];
        for(int i = 0; i <list.size(); i++){
            ret[i] = list.get(i);
        }
        return ret;
    }
}
